import java.text.DecimalFormat;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;

public class Insertion_Sorting {
    public static void main(String[] args) {
        Scanner in= new Scanner(System.in);

        System.out.println("请输入待排序队列个数：");
        int n=in.nextInt();

        int[] p=new int[n];//调用进程数据结构，设置进程数量

        System.out.println("请依次输入队列的值：");

        for(int i=0;i<n;i++){
            p[i]=in.nextInt();
        }

        System.out.println("未排序的的队列如下：");
        for (int i=0;i<n;i++){
            System.out.print(p[i]+"\t");
        }

        System.out.println();

       InsertSort(p);
        System.out.println("已排序的的队列如下：");
        for (int i=0;i<n;i++){
            System.out.print(p[i]+"\t");
        }
    }

    public static int[] InsertSort(int[] p){
          int j;
          int m;
          for (int i=0;i<p.length;i++){
            j=i;
            while (j>0){
                if(p[j]<p[j-1]){
                    m=p[j];
                    p[j]=p[j-1];
                    p[j-1]=m;
                }
                j--;
            }
          }
        return p;
    }

}
